package 排序算法.插入排序;

import java.util.Arrays;

/**
 * @Project: data-structure-and-algorithms
 * @Package: 排序.插入排序
 * @ClassName: shellSort
 * @Author: zhouyihe
 * @Date: 2025/11/12 17:14
 * @Description: 希尔排序
 */
public class shellSort {
    /**
     * 希尔排序是对插入排序的改进版本，更加高效，
     * 它的原理是比较相距一定间隔的元素，逐步减小间隔直到为1，此时数组已基本有序，再进行一次插入排序：
     * @param arr
     */
    public static void shellSort(int[] arr) {
        int n = arr.length;

        // 初始间隔设为n/2，每次减半
        for (int gap = n/2; gap > 0; gap /= 2) {
            // 对每个间隔进行插入排序
            for (int i = gap; i < n; i++) {
                int temp = arr[i];
                int j;

                // 对间隔为gap的元素进行插入排序
                for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
                    arr[j] = arr[j - gap];
                }

                arr[j] = temp;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {5, 4, 3, 2, 1};
        shellSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}
